package solution

import (
	"container/list"
	"fmt"
	"myleecode/solution/common"
	"time"
)

// 80. 删除排序数组中重复的项
// 原地删除
// 双指针
func Leecode80_removeDuplicates(nums []int) int {
	size := len(nums)
	//fill := nums[0] - 1
	if size <= 2 {
		return size
	}
	fmt.Println("origin: ", nums)
	c, i := 0, 0
	for j := 1; j < size; j++ {
		if nums[i] == nums[j] {
			c++
		} else {
			k := c - 1
			fmt.Println(i, j, k)
			if k > 0 {
				nums = append(nums[:j-k], nums[j:]...)
				size = size - k
				i = j - k
			} else {
				i = j
			}
			j = i
			c = 0
			//fmt.Println(i, j, c)
			fmt.Println(nums)
		}
	}
	if c-1 > 0 {
		nums = nums[:size-c+1]
	}
	return len(nums)
}

func Leecode81_search(nums []int, target int) bool {
	// TODO
	return false
}

// 82. 删除链表中重复的节点
// 不保留重复的接地那

func Leecode82_deleteDuplicates(head *common.ListNode) *common.ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var p *common.ListNode
	t := head
	head = nil
	count := 0
	head = nil
	for t != nil {
		if t.Next != nil {
			if t.Val == t.Next.Val {
				t = t.Next
				count++
				continue
			}

			if count == 0 {
				if p == nil {
					p = t
					head = p
				} else {
					p.Next = t
					p = t
				}
				t = t.Next
			} else {
				t = t.Next
				count = 0
			}

		} else {
			if count == 0 {
				if p == nil {
					p = t
					head = p
				} else {
					p.Next = t
					p = t
				}
			} else {
				if p == nil {
					return p
				}
				p.Next = nil
			}
			break
		}
	}
	return head
}

// 83. 删除排序链表中重复的元素
// 每个元素只能出现一次

func Leecode83_deleteDuplicate(head *common.ListNode) *common.ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var p *common.ListNode
	t := head
	count := 0
	_ = p
	for t != nil {
		if t.Next != nil {
			if t.Val == t.Next.Val {
				t = t.Next
				count++
				continue
			}

			if p == nil {
				p = t
				head = p
			} else {
				p.Next = t
				p = t
			}
			fmt.Println(t.Val)
			t = t.Next
		} else {
			if p == nil {
				p = t
				head = p
			} else {
				p.Next = t
				p = t
			}
			break
		}
	}

	return head
}

// 84 柱状图中最大的矩形

// 单调递增 + 栈
func Leecode84_largestRectangleArea(heights []int) int {
	size := len(heights)
	if size == 0 {
		return 0
	}
	if size == 1 {
		return heights[0]
	}
	ans := 0
	decr := 0
	stack := list.New()
	for i := 0; i < size; i++ {
		if stack.Len() == 0 {
			stack.PushFront(i)
			continue
		}

		e := stack.Front()
		h0 := e.Value.(int)
		if heights[i] >= heights[h0] {
			decr = 0
			stack.PushFront(i)
			//continue
		}
		if i+1 == size || heights[i] < heights[h0] {
			for j := 0; stack.Len() > 0; {
				e = stack.Front()
				h1 := e.Value.(int)
				if heights[i] >= heights[h1] {
					decr = 0
					break
				}
				if stack.Len() == 1 {
					decr++
					if ans < heights[h1] * decr {
						ans = heights[h1] * decr
					}
				}
				// heights[i] < heights[h]
				j++
				if ans < heights[h1]*j {
					ans = heights[h1] * j
				}
				stack.Remove(e)
			}
			stack.PushFront(i)
		}
	}

	//for j:=0; stack.Len() > 0; {
	//	e := stack.Front()
	//	h := e.Value.(int)
	//	if stack.Len() == 1 {
	//		if ans < heights[h] * size {
	//			ans = heights[h] * size
	//		}
	//	} else {
	//		j++
	//		if ans < heights[e.Value.(int)]*j {
	//			ans = heights[e.Value.(int)]*j
	//		}
	//	}
	//	stack.Remove(e)
	//}
	return ans
}

// 暴力算法: 时间复杂度O(N^2)
func Leecode84_largestRectangleArea2(heights []int) int {
	lenght := len(heights)
	ans := 0
	for i := 0; i < lenght; i++ {
		s := heights[i]
		for j := i + 1; j < lenght; j++ {
			if heights[i] > heights[j] {
				break
			}
			s += heights[i]
		}
		for j := i - 1; j >= 0; j-- {
			if heights[i] > heights[j] {
				break
			}
			s += heights[i]
		}
		if ans < s {
			ans = s
		}
	}
	return ans
}

// 86. 分割链表
func Leecode86_partition(head *common.ListNode, x int) *common.ListNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}
	t := head
	var p, b *common.ListNode
	for t != nil {
		if t.Val == x {
			p = t
		}
		if b == nil && t.Next != nil && t.Next.Val >= x {
			b = t
		}
		if p != nil && t.Next != nil && t.Next.Val < p.Val {
			q := t.Next
			t.Next = q.Next
			q.Next = head
			head = q
		}
		t = t.Next
		head.Print()
		if b != nil {
			fmt.Println(b.Val)
		}
		time.Sleep(1*time.Second)
	}
	return head
}

func Leecode88_merge(nums1 []int, m int, nums2 []int, n int)  {
	if n == 0 {
		return
	}
	i, j, k := 0, 0, 0
	result := make([]int, m+n)
	for  {
		//fmt.Println(i, j, m, n)
		if i == m {
			//fmt.Println(result[i+j:m+n], nums2[j:])
			copy(result[i+j:m+n], nums2[j:])
			break
		}
		if j == n {
			//fmt.Println(m+n-(i-j), i-j)
			copy(result[i+j:m+n], nums1[i:])
			break
		}
		if nums1[i] <= nums2[j] {
			result[k] = nums1[i]
			k++
			i++
		} else {
			result[k] = nums2[j]
			k++
			j++
		}
		fmt.Println(result)
		//time.Sleep(1*time.Second)
	}
	for i:=0; i<m+n; i++ {
		nums1[i] = result[i]
	}
}

// 89. 格雷编码
func Leecode89_grayCode(n int) []int {
	return nil
}
